package com.zp.self.module.level_4_算法练习.数据结构.二叉树;

import com.zp.self.module.level_4_算法练习.数据结构.链表.ListNode;
import org.junit.Test;

/**
 * @author By ZengPeng
 */
public class 力扣_109_有序链表转换二叉搜索树 {
    @Test
    public void main() {

        TreeNode treeNode = sortedListToBST(ListNode.getNode());
        System.out.println(treeNode);
    }

    /**
    题目：给定一个单链表的头节点  head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。
          本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。

     示例 1:
     输入: head = [-10,-3,0,5,9]
     输出: [0,-3,9,-10,null,5]
     解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。

     示例 2:
     输入: head = []
     输出: []

    分析：【P 💔💔💔】
       1.快慢指针:前面的放置左边，后面的放在右边 . -- 这样不行啊，有点节点没有右节点，导致超出2了
       2.转数组再构造：I.求长度，II.放数组 ,III.构建树
            --执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
            --时长：25分钟

    边界值 & 注意点：
       1.
     **/
    public TreeNode sortedListToBST(ListNode head) {
        int length=0;
        ListNode newHead = head;
        while (newHead!=null){
            length++;
            newHead = newHead.next;
        }
        int[] arr = new int[length];
        length=0;
        while (head!=null){
            arr[length++] = head.val;
            head = head.next;
        }
        return  dfs(arr,0,length-1);
    }

    private TreeNode dfs(int[] arr, int start, int end) {
        if(start>end) return null;
        if(start==end) return  new TreeNode(arr[start]);
        int mid = start+(end-start)/2;
        TreeNode top = new TreeNode(arr[mid]);
        top.left = dfs(arr,start,mid-1);
        top.right = dfs(arr,mid+1,end);
        return top;
    }
}
